package hot100.logos41To50;

import hot100.datastruct.TreeNode;

/**
 * @author logos
 * date 2025/7/14 17:44
 * @version v1.0
 * @Package hot100.logos41To50
 */
public class logos50 {

    /**
     * 50. 二叉树中的最大路径和
     * https://leetcode.cn/problems/binary-tree-maximum-path-sum/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public int ans = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            dfs(root);
            return ans;
        }

        public int dfs(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int lval = dfs(root.left);
            int rval = dfs(root.right);
            ans = Math.max(ans, lval + rval + root.val);
            return Math.max(Math.max(lval, rval) + root.val, 0);
        }
    }
}
